package exercises.newcoder.solution;

/**
 * <a href="https://www.nowcoder.com/practice/166eaff8439d4cd898e3ba933fbc6358?tpId=188&&tqId=38657&rp=1&ru=/activity/oj&qru=/ta/job-code-high-week/question-ranking">
 * NC34 求路径</a>
 * <img src="https://uploadfiles.nowcoder.com/images/20201210/999991351_1607596327517/873CB1F2327F70DA0CA0FDC797F894A7">
 *
 * @author or2
 * @Description 一个机器人在m×n大小的地图的左上角（起点）。
 * 机器人每次向下或向右移动。机器人要到达地图的右下角（终点）。
 * 可以有多少种不同的路径从起点走到终点？
 * @create 2021年09月18日 时间: 17:10
 */
public class UniquePaths {
    /**
     * @param m int整型
     * @param n int整型
     * @return int整型
     */
    public int uniquePaths(int m, int n) {
        int[][] route = new int[m][n];
        for (int i = 0; i < n; i++) {
            route[0][i] = 1;
        }
        for (int i = 0; i < m; i++) {
            route[i][0] = 1;
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                route[i][j] = route[i - 1][j] + route[i][j - 1];
            }
        }

        return route[m - 1][n - 1];
    }
}
